#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
#define LeftChild(i) (2*(i)+1)

class Point {
public:
    Point(int x = 0, int y = 0) : _ix(x), _iy(y) {}

    Point(const Point &point) : _ix(point._ix), _iy(point._iy) {}

    double getDistance() const {
        return hypot(_ix, _iy);
    }

    int getX() const {
        return _ix;
    }

    int getY() const {
        return _iy;
    }

    friend ostream &operator<<(ostream &os, const Point &rhs);

private:
    int _ix;
    int _iy;
};
// TODO 方式一：特化模板

// TODO 方式二：运算符重载

/**
 * 方式三：函数对象
 */
struct Compare{
    bool operator()(const Point &lhs, const Point &rhs){
        return lhs.getDistance() < rhs.getDistance();
    }
};





ostream &operator<<(ostream &os, const Point &rhs) {
    return os << "(" << rhs._ix << "," << rhs._iy << ")";
}


template<typename T, typename Compare = std::less<T>>
class HeapSort {
private:
    vector<T> _vec;
    Compare _cmp;

public:
    HeapSort(T *arr, size_t size, Compare cmp = Compare()) :
            _vec(arr, arr + size), _cmp(cmp) {}

    void sort() {
        int i;
        size_t N = _vec.size();

        for (i = (N - 1) / 2; i >= 0; i--) {
            percolateDown(i, N);
        }
        for (i = N - 1; i > 0; i--) {
            std::swap(_vec[0], _vec[i]);
            percolateDown(0, i);
        }

    }

    void print() const {
        for (auto &elem: _vec) {
            std::cout << elem << " ";
        }
        std::cout << std::endl;
    }

private:

    void percolateDown(int i, size_t N) {
        size_t child;
        T tmp;

        for (tmp = _vec[i]; LeftChild(i) < N; i = child) {
            child = LeftChild(i);
            if (child != N - 1 && _cmp(_vec[child], _vec[child + 1])) {
                child++;
            }

            if (_cmp(tmp, _vec[child])) {
                _vec[i] = _vec[child];
            } else {
                break;
            }
        }
        _vec[i] = tmp;
    }


};


int main() {

    Point points[] = {{5, 12}, {3, 4}, {2, 2}, {3, 4}};
    size_t len = sizeof(points) / sizeof(points[0]);

    /**
     * less:小顶堆
     * greater:大顶堆
     */
    HeapSort heapSort(points, len, Compare());
    heapSort.sort();
    heapSort.print();
    return 0;
}
